This invention relates to cryptography and, more particularly, to a method of passing a cryptographic key so that an authorized third party may gain access to the key.
Practitioners in the field of cryptography first occupied themselves with trying to find a mathematical function that an adversary could not determine. Theoretically, such functions exist (e.g., scramblers). However, such devices are not secure because such devices are easily reverse-engineered in order to determine the cryptographic function.
The notion that hardware could be kept secret was abandoned. An idea was then introduced to couple a secret random entity (i.e., a cryptographic key) to the hardware in order to keep communications secure even if the hardware was reverse engineered. In this scenario, each user received a copy of the hardware. Each pair, or group, of users who wished to communicate securely would decide on a cryptographic key. For convenience, the process was such that the cryptographic key could be used for both encryption and decryption hence the terms xe2x80x9csymmetric-keyxe2x80x9d and xe2x80x9csymmetric-key cryptography.xe2x80x9d The cryptographic key decided upon was then securely given to each party to the communication. Typically, this meant that the cryptographic key had to be securely delivered to each user. Such a key distribution system works well with a closed group of users consisting of a small number, but it becomes unwieldy when the number of users is large. Also, if the symmetric-key is compromised, the communications of everyone using the key is compromised. Therefore, a need arose for a solution to the key distribution problem. Public-key cryptography offers such a solution.
U.S. Pat. No. 4,200,770, entitled xe2x80x9cCRYPTOGRAPHIC APPARATUS AND METHOD,xe2x80x9d is a patent on the first publicly disclosed method of arriving at a secret symmetric-key between two users using a non-secure channel. U.S. Pat. No. 4,200,770, commonly referred to as the Diffie-Hellman key exchange method, is hereby incorporated by reference into the specification of the present invention. In this key exchange method, each user generates a random number that is kept secret. Each user uses their secret as an exponent to a non-secret base that is shared in common with the other user (i.e., exponentiation). Each user modulo reduces their exponentiation by a non-secret number that is shared in common with the other user. Each user transmits their modulo reduced exponentiation to the other user. Each user raises the exponentiation they receive to their secret, and each user modulo reduces this second exponentiation by the same shared modulus. This results in each user computing the same value that is known only by them. In effect, each user conceals their secret (the exponent) in a mathematical function that is believed to be unsolvable for large values (i.e., modulo reduced exponentiation). Each user transmits their buried secret to the other user. Each user raises the other user""s buried secret to their secret. After a final modulo reduction, each user is in possession of the same symmetric key that an adversary cannot mathematically determine. To mathematically determine the key, an adversary must be able to determine the discreet logarithm of what at least one user transmitted, hence the name xe2x80x9cdiscreet logarithm problem.xe2x80x9d This problem is considered unsolvable, or intractable, for large values.
Here, xe2x80x9ckey exchangexe2x80x9d is defined as each user participating in the creation of a key. Neither participant knows in advance what the final key will be. This differs from a xe2x80x9ckey passxe2x80x9d which entails a single user creating a key and passing it securely to the other user. The receiving user recovers, or decrypts, the key but does not alter the key in any other way.
Along with the advantages of public-key cryptography there are some disadvantages. That is, public-key cryptography involves many more steps than does symmetric-key cryptography. This means that public-key cryptography is slow compared to symmetric-key cryptography. Also, a user using the Diffie-Hellman key exchange method cannot be sure that the other user is who they claim to be. Therefore, a need arose for a method of digitally signing an electronic communication.
Taher ElGamal, in a paper entitled xe2x80x9cA Public Key Cryptosystem and Signature Scheme Based on Discreet Logarithms,xe2x80x9d IEEE Transactions on Information Theory, Vol. IT-31, No. 4, July 1985, pp. 469-472, proposed an encryption method and a digital signature method that incorporates the strength of the Diffie Hellman key-exchange method (i.e., the discreet logarithm problem). ElGamal""s signature method has received more attention than has his encryption method. ElGamal""s signature method is based on Euler""s Totient function. In this method, a first user generates a long term secret exponent and xe2x80x9chidesxe2x80x9d it in a modulo reduced exponentiation using a publicly known base and modulus. The user binds the result to his or her identity by a certifying authority. Next, the first user computes a number using a certain parameter (e.g. a message), his long-term secret, and a second per-message secret. These two secrets are known only by the first user. The first user sends the computed number, the modulo reduced exponentiation of the xe2x80x9cper-message secret,xe2x80x9d and the message to the second user. The second user uses the numbers, the message, and the certified modulo reduced exponentiation to verify a mathematical relationship. If the relationship is verified then the second user is assured that the message came from the first user. This may not be true if the long-term secret is known by an adversary. ElGamal""s method creates a digital signature. The computations involved here are mathematically complex and time consuming. The resulting signature is large and requires a large amount of bandwidth in order to transmit it.
In a paper entitled xe2x80x9cEfficient Identification and Signatures for Smart Cards,xe2x80x9d Advances in Cryptologyxe2x80x94Proceedings of CRYPTO ""89, Lecture Notes in Computer Science, No. 435, Springer-Verlag, New York, 1990, pp. 239-251, Claus Schnorr developed a variation of ElGamal""s digital signature that is simpler to compute and takes up less bandwidth than ElGamal""s digital signature. Schnorr uses a subgroup of the group used by ElGamal. The subgroup Schnorr uses is smaller than the group used by ElGamal. The result is a faster, less compute intensive method that requires fewer bits to be transmitted. Schnorr""s method was patented as U.S. Pat. No. 4,995,082 entitled xe2x80x9cMETHOD FOR IDENTIFYING SUBSCRIBERS AND FOR GENERATING AND VERIFYING ELECTRONIC SIGNATURES IN A DATA EXCHANGE SYSTEM.xe2x80x9d U.S. Pat. No. 4,995,082 is hereby incorporated by reference into the specification of the present invention.
The National Institute of Standards and Technology (NIST) published Federal Information Process Standard (FIPS) Publication No. 186 entitled xe2x80x9cDigital Signature Standardxe2x80x9d (DSS). FIPS PUB 186 is hereby incorporated by reference into the specification of the present invention. The DSS discloses a method of generating a digital signature that is secure, reasonably easy to generate and verify, and bandwidth efficient. U.S. Pat. No. 5,231,668, entitled xe2x80x9cDigital Signature Algorithm,xe2x80x9d (DSA) embodies DSS. U.S. Pat. No. 5,231,668 is hereby incorporated by reference into the specification of the present invention. DSA is a bandwidth efficient variant of ElGamal. DSA employs the computations of ElGamal in a subgroup of the group used by ElGamal. The subgroup used in DSA is smaller than the group used by ElGamal.
In a paper entitled xe2x80x9cMessage Recovery for Signature Schemes Based on the Discreet Logarithm Problem,xe2x80x9d Pre-proceedings of Eurocrypt ""94, pp. 175-190, Ms. Nyberg and Mr. Rueppel developed a variant of DSA that eliminates the need to send the message while allowing the recovery of the message from what is transmitted. Nyberg and Rueppel also propose a key exchange method that is based on DSA and the Diffie-Hellman key exchange method. The steps of their message-recovery method is as follows:
a) a first user generates two random integers xe2x80x9ck1xe2x80x9d and xe2x80x9ck2,xe2x80x9d where xe2x80x9ck1xe2x80x9d and xe2x80x9ck2xe2x80x9d are each less than a prime integer xe2x80x9cq,xe2x80x9d where xe2x80x9cqxe2x80x9d divides evenly into xe2x80x9cpxe2x88x921,xe2x80x9d where xe2x80x9cpxe2x80x9d is a prime integer greater than xe2x80x9cqxe2x80x9d;
b) the first user computes xe2x80x9cr1=g{circumflex over ( )}(k2xe2x88x92k1) mod p,xe2x80x9d where xe2x80x9c{circumflex over ( )}xe2x80x9d denotes exponentiation, and where the base xe2x80x9cgxe2x80x9d has order xe2x80x9cqxe2x80x9d in the integers modulo xe2x80x9cpxe2x80x9d;
c) the first user computes xe2x80x9cr2=r1 mod qxe2x80x9d;
d) the first user solves the equation xe2x80x9c1=((xe2x88x92x1*r2)+(k1*s)) mod q,xe2x80x9d for xe2x80x9csxe2x80x9d, where xe2x80x9cx1xe2x80x9d is the first user""s long-term secret, and where xe2x80x9c*xe2x80x9d denotes multiplication;
e) the first user transmits (r1, s) to a second user;
f) the second user computes xe2x80x9cr2=r1 mod qxe2x80x9d;
g) the second user computes xe2x80x9ct=(1/s) mod q,xe2x80x9d and xe2x80x9c(((g{circumflex over ( )}x1){circumflex over ( )}r2)*g){circumflex over ( )}t mod p,xe2x80x9d where this last computation should equal xe2x80x9cg{circumflex over ( )}k1 mod pxe2x80x9d;
h) the second user then computes xe2x80x9c(g{circumflex over ( )}k2)*r1 mod pxe2x80x9d, where the result should equal xe2x80x9cg{circumflex over ( )}k2 mod pxe2x80x9d;
i) the second user computes xe2x80x9ckey=(g{circumflex over ( )}k2){circumflex over ( )}x2 mod p,xe2x80x9d where xe2x80x9cx2xe2x80x9d is the second user""s long-term secret; and
j) the second user sends xe2x80x9cg{circumflex over ( )}x2 mod pxe2x80x9d to the first user; and
k) the first user computes xe2x80x9ckey=((g{circumflex over ( )}x2) mod p){circumflex over ( )}k2 mod p.xe2x80x9d
Note that the equation in step (d) is the same as the equation in DSA with the value xe2x80x9czxe2x80x9d in DSA set to one. The pair xe2x80x9c(r1, s)xe2x80x9d embodies not just the signature of a message, but includes the message itself. The second user recovers the message and verifies the source as the first user. Both users will be able to compute xe2x80x9ckeyxe2x80x9d only if they know their respective long term secrets.
The message-recovery method of Nyberg and Rueppel does not allow the recovery of a key by an authorized third party and it requires the transmission of the long value xe2x80x9cr1.xe2x80x9d
In a paper entitled xe2x80x9cMETA-ElGamal Signature Schemes,xe2x80x9d 2nd ACM Conference on Computer and Communications Security, 1994, Messrs. Horster, Petersen, and Michels disclose a general equation (i.e., A=(xB+kC) mod q) for the three DSS parameters xe2x80x9cmxe2x80x9d, xe2x80x9crxe2x80x9d, and xe2x80x9cs.xe2x80x9d The parameter xe2x80x9cmxe2x80x9d denotes the hash of a message to be signed, the signer""s long-term secret xe2x80x9cx,xe2x80x9d and the signer""s per-signature secret xe2x80x9ck.xe2x80x9d The parameter xe2x80x9crxe2x80x9d is computed as xe2x80x9cr=(g{circumflex over ( )}k mod p) mod q.xe2x80x9d Horster et al. disclose six different signature equations that were generated by six different ways of substituting (m,r,s) for (A,B,C). The six different signature equations are as follows:
m=xAr+ks mod q, where A=m, B=r, and C=s;
m=xAs+kr mod q, where A=m, B=s, and C=r;
s=xAr+km mod q, where A=s, B=r, and C=m;
s=xAm+kr mod q, where A=s, B=m, and C=r;
r=xAs+km mod q, where A=r, B=s, and C=m; and
r=xAm+ks mod q, where A=r, B=m, and C=s.
Horster et al. also disclose a general verification equation (i.e., xcex1A=(yA)BrC mod p) for the general signature equation. The six different verification equations that correspond to the six signature equations above are as follows:
xcex1m=(yA)rrs mod p, where A=m, B=r, and C=s;
xcex1m=(yA)srr mod p, where A=m, B=s, and C=r;
xcex1s=(yA)rrm mod p, where A=s, B=r, and C=m;
xcex1s=(yA)mrr mod p, where A=s, B=m, and C=r;
xcex1r=(yA)srm mod p, where A=r, B=s, and C=m; and
xcex1r=(yA)mrs mod p, where A=r, B=m, and C=s.
The present invention improves upon these general equations by including a method of recovering the key by a third party.
A cryptographic method that allows third party access to an encrypted communication has been proposed. Such a method is called xe2x80x9ckey escrow.xe2x80x9d Essentially, key escrow is a cryptographic method that allows a third party (e.g., a law enforcement activity) access to the key used by a first user and a second user when the third party is authorized to do so (e.g., when criminal activity is suspected and a search warrant is obtained). U.S. Pat. Appl. No. 08/528,966, entitled xe2x80x9cA DEVICE FOR AND METHOD OF CRYPTOGRAPHY THAT ALLOWS THIRD PARTY ACCESS, now U.S. Pat. No. 5,631,961,xe2x80x9d is an example of such a method. U.S. Pat. Appl. No. 08/528,966 is hereby incorporated by reference into the specification of the present invention. One of the problems with the proposed key-escrow methods is that the key escrow aspect of the pass or exchange is independent of the key establishment process. This separation makes the method vulnerable to attacks that would not be possible if the key escrow were made an integral part of key establishment process. The present invention discloses a method that allows a first user to pass a cryptographic key to a second user which incorporates a key-escrow feature.
It is an object of the present invention to pass a cryptographic key from a first user to a second user so that an authorized third party may gain access to the key.
It is another object of the present invention to pass a cryptographic key from a first user to a second user in a certified and bandwidth efficient manner so that an authorized third party may gain access to the key.
It is another object of the present invention to exchange a cryptographic key between a first user and a second user so that an authorized third party may gain access to the key.
It is another object of the present invention to exchange a cryptographic key between a first user and a second user in a certified and bandwidth efficient manner so that an authorized third party may gain access to the key.
The present invention is a method of passing a key between a first user and a second user in a manner that allows an authorized third party to gain access to the key.
In the present invention, key recovery is embedded into the key pass method. Key recovery allows an authorized third party to recover the key with the help of an escrow agent.
The steps of the present invention are as follows:
a) a first user generates a first random number xe2x80x9ck1axe2x80x9d;
b) the first user generates xe2x80x9ckey1=m(k1a)xe2x80x9d;
c) the first user generates a second random number xe2x80x9ck2axe2x80x9d;
d) the first user computes xe2x80x9cy1=m(hp2(k2a))xe2x80x9d;
e) the first user computes xe2x80x9cy2=m(Hp(k1a));
f) the first user computes xe2x80x9cr1=f(y1,k1a)xe2x80x9d;
g) the first user computes xe2x80x9cz=f(y2, key1)xe2x80x9d;
h) the first user computes xe2x80x9cs=(1/k2a) ((k1a*z)+(xa*r1)) mod q,xe2x80x9d;
i) the first user computes xe2x80x9cG=g{circumflex over ( )}k1a mod pxe2x80x9d;
j) the first user passes (G,z,r1,s) to the second user;
k) the second user receives xe2x80x9cY=g{circumflex over ( )}xa mod pxe2x80x9d from, for example, an independent directory/certificate server;
l) the second user computes xe2x80x9cT=(Y{circumflex over ( )}r1*G{circumflex over ( )}z){circumflex over ( )}((1/s) mod q) mod pxe2x80x9d;
m) the second user computes xe2x80x9cy1=m(ha2(T))xe2x80x9d;
n) the second user computes xe2x80x9ck1a=(fxe2x88x921) (y1, r1),xe2x80x9d;
o) the second user computes xe2x80x9ckey1=m(k1a)xe2x80x9d;
p) a third party intercepts (G,z,r1,s) transmitted from the first user to the second user;
q) the third party presents xe2x80x9cGxe2x80x9d and xe2x80x9czxe2x80x9d to a key-escrow agent;
r) the key-escrow agent computes xe2x80x9cy2=m(Hs(G))xe2x80x9d:
s) the key-escrow agent computes xe2x80x9ckey2=(fxe2x88x921)(y2, z), where key2=key1xe2x80x9d; and
t) the key escrow agent returns xe2x80x9ckey2xe2x80x9d to the third party if the third party is authorized to receive xe2x80x9ckey2xe2x80x9d; and
u) the third party uses xe2x80x9ckey2xe2x80x9d to decrypt an encrypted message sent between the first user and the second user which was encrypted using xe2x80x9ckey1.xe2x80x9d
In an alternate embodiment, steps may be added to the method above that would allow the second user to determine if the first user is complying with escrow aspects of the method. In the method above, the second user is given or computes terms that may be used to generate other terms transmitted from the first user to the second user. The second user may compute certain terms transmitted from the first user to the second user and compare these computed terms to the terms transmitted. The method continues if the compared terms are the same and is halted otherwise. The following five steps may be inserted after step (o) above:
o1) the second user computes xe2x80x9cy2=m(Hp(k1a))xe2x80x9d;
o2) the second user computes xe2x80x9cz=f(y2, key);
o3) the second user compares xe2x80x9czxe2x80x9d computed in step (o2) to xe2x80x9czxe2x80x9d received from the first user, if they match, the method continues, otherwise the method is halted;
o4) the second user computes xe2x80x9cG=g{circumflex over ( )}k1a mod pxe2x80x9d; and
o5) the second user compares xe2x80x9cGxe2x80x9d computed in step (o4) to xe2x80x9cGxe2x80x9d received from the first user, if they match, the method continues, otherwise the method is halted.
In a second alternate embodiment, xe2x80x9czxe2x80x9d may be formed using a portion of xe2x80x9ckey1xe2x80x9d instead of all of xe2x80x9ckey1xe2x80x9d. Also, more than one key-escrow agent may be employed, and many different scenarios are possible with respect to what these escrow agents hold. Additional certification and identification schemes may be incorporated into the present invention if desired.
A third alternate embodiment of the present invention is a key exchange method that allows an authorized third party to obtain a key exchanged between a first user and a second user. In the key-exchange method, a first user and a second user each generate and pass their own key as above to the other user. That is, the first user generates a key and passes it to the second user while the second user generates a different key and passes it to the first user. Each user then combines the two keys in an agreed upon fashion to arrive at the final key to be used to encrypt messages between the users. That is, each user combines the key that they generated and passed to the other user to the key that was passed to them by the other user. The authorized third party would then have to intercept the two key messages transmitted between the users, recover both keys, and combine them in the same manner the users did.
The preferred embodiment of the present invention results in a bandwidth efficient method of passing a key from a first user to a second user while allowing an authorized third party access to the key. The present invention is less susceptible to attack than methods that separate key establishment from key escrow.